﻿#define  _CRT_SECURE_NO_WARNINGS 1

//1.1.相交链表
typedef struct ListNode ListNode;
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    //求链表长度
    ListNode* pa = headA;
    ListNode* pb = headB;
    int sizeA = 0, sizeB = 0;
    while (pa)
    {
        ++sizeA;
        pa = pa->next;
    }
    while (pb)
    {
        ++sizeB;
        pb = pb->next;
    }
    //求链表长度差
    int gap = abs(sizeA - sizeB);//得到的是绝对值
    //定义长短链表
    //假设
    ListNode* shortlist = headA;
    ListNode* longlist = headB;
    if (sizeA > sizeB)
    {
        longlist = headA;
        shortlist = headB;
    }
    //长链表往前遍历
    while (gap--)
    {
        longlist = longlist->next;
    }
    //两链表一起走
    while (shortlist && longlist)
    {
        if (shortlist == longlist)
        {
            return shortlist;
        }
        shortlist = shortlist->next;
        longlist = longlist->next;
    }
    //不相交
    return NULL;
}

//2.环形链表
//思路一：
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            return true;
        }
    }
    return false;
}
//思路二：
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode* head) {
    ListNode* slow, * fast;
    slow = fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        int n = 3; //fast每次⾛三步
        while (n--)
        {
            if (fast->next)
                fast = fast->next;
            else
                return false;
        }
        if (slow == fast)
        {
            return true;
        }
    }
    return false;
}

//3.环形链表II
typedef struct ListNode ListNode;
struct ListNode* detectCycle(struct ListNode* head) {
    //创建快慢指针
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            //相遇点:使用curr == slow，不动head,且使curr与slow一样每次走一步
            ListNode* curr = head;
            while (curr != slow)
            {
                curr = curr->next;
                slow = slow->next;
            }
            //入环第一个结点
            return curr;
        }
    }
    //不带环
    return NULL;
}

//4.链表分割
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        //定义两链表
        ListNode* lessHead, * lessTail;
        lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));
        ListNode* greaterHead, * greaterTail;
        greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));
        //遍历
        ListNode* curr = pHead;
        while (curr)
        {
            //尾插到小链表
            if (curr->val < x)
            {
                lessTail->next = curr;
                lessTail = lessTail->next;
            }
            else {
                //尾插到大链表
                greaterTail->next = curr;
                greaterTail = greaterTail->next;
            }
            curr = curr->next;
        }
        //大链表尾结点置空
        greaterTail->next = NULL;
        //相连
        lessTail->next = greaterHead->next;
        ListNode* ret = lessHead->next;
        free(lessHead);
        free(greaterHead);
        return ret;
    }
};

//5.随机链表的复制
typedef struct Node Node;
//申请结点
Node* buyNode(int x)
{
    Node* newnode = (Node*)malloc(sizeof(Node));
    newnode->val = x;
    newnode->next = newnode->random = NULL;
    return newnode;
}
//增加结点
void AddNode(Node* head)
{
    Node* curr = head;
    while (curr)
    {
        //创建一样的结点
        Node* newnode = buyNode(curr->val);
        Node* next = curr->next;//此处next用于保存原链表下一结点
        //插入  
        newnode->next = next;
        curr->next = newnode;
        curr = next;
    }
}
//放置random
void setRandom(Node* head)
{
    Node* curr = head;
    while (curr)
    {
        Node* copy = curr->next;
        if (curr->random)
            copy->random = curr->random->next;
        curr = copy->next;
    }
}

struct Node* copyRandomList(struct Node* head) {
    if (head == NULL)
    {
        return head;
    }
    //(1)
    AddNode(head);
    //(2)
    setRandom(head);
    //(3)
    Node* curr = head;
    Node* copyHead, * copyTail;
    copyHead = copyTail = curr->next;
    while (copyTail->next)
    {
        curr = copyTail->next;
        copyTail->next = curr->next;
        copyTail = copyTail->next;
    }
    return copyHead;
}